class Solution:
    def minCost(self, n: int, cuts: list[int]) -> int:
        cuts.append(0)
        cuts.append(n)
        cuts.sort()
        DP = [[-1 for __ in range(len(cuts))] for _ in range(len(cuts))]

        def dp(left: int, right: int) -> int:
            if left < 0 or right >= len(cuts):
                return 0

            if left >= right:
                return 0

            if right - left == 1:
                return 0

            if DP[left][right] != -1:
                return DP[left][right]

            disk = cuts[right] - cuts[left]
            for i in range(left + 1, right):
                temp = disk + dp(left, i) + dp(i, right)
                DP[left][right] = temp if temp < DP[left][right] or DP[left][right] == -1 else DP[left][right]

            return DP[left][right]

        return dp(0, len(cuts) - 1)
